package Algorithm;

import java.awt.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author yyq
 * @create 2022-01-25 16:19
 *  汉诺塔
 *  实现  A塔 --->   C塔
 *
 *  塔A 塔B 塔C
 *
 *  这里采用分治法
 *
 *  分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
 *  解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
 *  合并：将各个子问题的解合并为原问题的解。
 *
 *  这里面临的情况
 *
 *  情况1：
 *
 *  如果是有一个盘， A->C
 *
 * 情况2：
 *
 *  如果我们有 n >= 2 情况，我们总是可以看做是两个盘
 *   1.最下边的盘 2. 上面的盘
 *
 * 		先把 最上面的盘 A->B
 * 		把最下边的盘 A->C
 * 	    把B塔的所有盘 从 B->C
 *
 */
public class Hannota {
    public static void main(String[] args) {
        hannota(3,'a','b','c');

    }
    // num 代表盘子的个数
    public static void hannota(int num,char a,char b,char c){
        // 如果此时只有一个盘时
        if(num == 1){
            System.out.println("第"+num+"层"+a+"->"+c);
        }
        // 如果多于两个盘 看作只有两个盘 1 最下面的盘 2 其余的盘
        else {
            // 1 首先要把 其余的盘挪到 b
            hannota(num-1,a,c,b);
            // 2 其次把 最下面的盘挪到 c
            System.out.println("第"+num+"层"+a+"->"+c);
            // 3 把 把其余的盘挪到c
            hannota(num-1,b,a,c);
        }
    }

}
